package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;


import sun.tools.jar.resources.jar;
import util.LogUtils;

/*
 * 
原题　
		Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
	
	For example,
	Given n = 3, there are a total of 5 unique BST's.
	
	   1         3     3      2      1
	    \       /     /      / \      \
	     3     2     1      1   3      2
	    /     /       \                 \
	   2     1         2                 3
题目大意
	给定n，存储值1 ... n的结构独特的BST（二进制搜索树）有多少？
	
	例如，
	给定n = 3，共有5个独特的BST。

解题思路
	//参考资料
	http://www.cnblogs.com/grandyang/p/4299608.html
		就跟斐波那契数列一样，我们把n = 0 时赋为1，因为空树也算一种二叉搜索树，那么n = 1时的情况可以看做是其左子树个数乘以右子树的个数，左右字数都是空树，所以1乘1还是1。那么n = 2时，由于1和2都可以为跟，分别算出来，再把它们加起来即可。n = 2的情况可由下面式子算出：
	
	
	
	dp[2] =  dp[0] * dp[1]　　　(1为根的情况)			
	
	　　　　+ dp[1] * dp[0]　　  (2为根的情况)
	
	同理可写出 n = 3 的计算方法：
	
	dp[3] =  dp[0] * dp[2]　　　(1为根的情况)
	
	　　　　+ dp[1] * dp[1]　　  (2为根的情况)
	
	 　　　  + dp[2] * dp[0]　　  (3为根的情况)
	
	由此可以得出卡塔兰数列的递推式为：


 * @Date 2017-09-24 22：30
 */
public class _096_Unique_Binary_Search_Trees {
	
    public int numTrees(int n) {
    	if (n < 0)			return 0;
    	int[] dp = new int[n+1];
    	dp[0] = 1;			//空树也是一种状态
    	dp[1] = 1;			//一个节点的树，只有一种状态	即：左子树状态(空树为1) * 右子树状态(空树为1)
    	for (int i = 2; i <= n; i ++) {
    		for (int j = 0; j < i; j ++) {
    			dp[i] += dp[j]*dp[i-j-1];
    		}
    	}
        return dp[n];
    }

	public static void main(String[] args) {
		_096_Unique_Binary_Search_Trees obj = new _096_Unique_Binary_Search_Trees();

		LogUtils.println("独一无二树", obj.numTrees(5));
	}

}
